package main.leetcode.primary.from001to100;

import main.datastruc.ListNode;

/**
 * 24.两两交换链表中的节点
 *
 * <p>给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *
 * <p>你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * <p>
 *
 * <p>示例:给定 1->2->3->4, 你应该返回 2->1->4->3.
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex24 {
    public static void main(String[] args) {
        ListNode head = ListNode.creList(new int[] {1, 2, 3, 4});
        System.out.println(new ex24().swapPairs(head));
    }

    // 递归
    //    public ListNode swapPairs(ListNode head) {
    //        if (head == null || head.next == null) {
    //            return head;
    //        }
    //        ListNode res = new ListNode(-1);
    //        ListNode node = head.next;
    //        res.next = node;
    //        head.next = swapPairs(node.next);
    //        node.next = head;
    //        return res.next;
    //    }

    // 迭代
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode res = new ListNode(-1);
        //        res.next = head;
        ListNode pre = res;
        ListNode node, next;
        while (head != null && head.next != null) {
            node = head;
            next = node.next;

            pre.next = next;
            node.next = next.next;
            next.next = node;

            pre = node;
            head = node.next;
        }
        return res.next;
    }
}
